package leetcode100;

// TODO 中序遍历 | 二叉树 [经典] 【-】 二叉树的中序遍历
// TODO https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/shou-hua-tu-jie-yong-zhan-mo-ni-zhong-xu-bian-li-z/

import java.util.ArrayList;
import java.util.List;

public class lc100_0094 {

    List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);

        return res;
    }

    public void dfs(TreeNode node) {
        // 递归终止条件
        if (node == null)
            return;

        // 保存结果 + 继续递归
        dfs(node.left);
        res.add(node.val);
        dfs(node.right);
    }

}